(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Remarks on the Status of Inference in the Area of Knowledge Representation"

ISSN 0281-9864 



Remarks on the Status of Inference 

in the Area of 

Knowledge Representation 

Christopher Habel 




KOGNITIONSVETENSKAPLIG 
FORSKNING 

Cognitive Science Research 



Lund University 
Sweden 



Remarks on the Status of Inference 
tn the Area of ■■ 

Knowledge Representation 

Christopher Habel 



1987 No. 20 



Communications should be sent to: 

Bernhard Bierschenk 

Department of Psychology 

Paradisgatan 5 

Lund University 

S-22350 Lund, Sweden 



Abstract 



The concept of inference Is one of the global concepts used for the 
explanation of cognitive processes. There. exist mainly two types of 
characterization: the logical and the psychological. These different 
characterizations are based on the difference between inference and rule 
of inference . 

Information processing systems can be formalized as inferential 
systems, i.e. systems with inferential processes. The fundamental 
concepts of this formalization, those of dynamical inferential systems 
and time-restricted derivations, both based on inferential processes are 
described in detail. '■'-'■ ' 



Remarks on the status of Inference in the area of 
Knowledge Representation 



i» 



1. Preliminaries on Cognitive Science 

One of the fundamentals of Cognitive Science (CS) - and thus of Cognitive 
Psychology and Ari:ificial Intelligence (Al) - is the view of minds as 
information processing systems (IPS), cp. Haugeland (1978). The 
strongest, i.e. most far-reaching, version of Cognitivism can be 
characterized by Newell's (1980) 

Physical Symbol System Hypothesis 

"... humans are instances of physical symbol systems, and by 
virtue of this, mind enters into the physical universe." (p. 136) 

Thus the subject in Cognitive Science is the inquiry of information 
processes from different points of view and with different goals. 
Considering the whole spectrum from Cognitive Psychology to applied 
Artificial Intelligence this leads to such different goals as the 
explanation of processes in the human mind, on one hand, and the use of 
information processes in applied Al-systems, on the other hand. (The 
current state of the art is dominated by a strategy of investigation, 
which Church! and (1984; p. 106) characterizes - w.r.t. Al - as the 
"piecemeal approach": only very specific processes are investigated; a 
global view of the whole phenomenon of human intelligence is out of the 
range of our scientific knowledge yet.) Analogously we also have a 
spectrum of experiments to lay an empirial base for the investigation of 
mind. This reaches from experiments with natural subjects (human or 
animals) in the psychological tradition to computer systems in the 
simulation mode. (From now on I will neglect the application-oriented 
parts of Al and therefore the application mode of Al-systems too.) Later 
on in the present paper I will sketch a third type of evidences, which 
could be called theoretical evidences . Such evidences are only possible 
by virtue of strict formalisms. And at this point, two older relatives of 
the twins Cognitive Psychology and Artificial Intelligence, namely 
Mathematics and Logics, will enter the stage. 

Following the information processing paradigm of the human mind it is 
necessary to postulate system-internal models of real or fictional 
worlds. These internal models are built up by (formal) knoyyledge entities 
on a semantic or intentional level. (On this level cp. Pylyshyn 1984; p. 
210-21 1). Beyond these representations, procedures {procedure is used 
here in a non-technical sense) are needed to work on the representations. 
By this the subject area in Representation of KnovyJedge can be outlined: 
the investigation of these representations and the operations on them to 
change the internal models. 



2. Inferences 

In the present section I will give ennphasis to the most relevant (from my 
point of view) concept in the area of knowledge representation: inference. 
The concept of inference is one of the global concepts (see above) used 
for the explanation of general cognitive processes. The notion of 
inference can be found all over Cognitive Science but without a unique 
and well-established definition. There exist mainly two types of 
characterization; 

the logical characterization: 

THE RULES OF INFERENCE amount to directions as to how sentences 

already known as true may be transformed so as to yield new true 
sentences." (Tarski, 1965; p. 47) 

the psychological characterization: 

The process of a conclusion, or a conclusion reached, on the basis of 
previously made or accepted judgements." (Drever, 1964; p. 136.) 

These roots lead to a converged A I characterization (or one of forms! 
Cognitive Science ): 

"Inferences are well-defined changes of attitudes to knowledge 
entities" 

At this point one important distinction has to be called to notice, namely 
that between the concepts rule of inference and inference . The former 
refers to an instruction or advice how to move from a set of attitudes to 
some knowledge entities to another set of attitudes to the same or other 
knowledge attitudes. This means, that rules of inference can be seen as 
inference-tickets . which license the change of attitudes. (The notion of 
inference-ticket is due to G.Ryle (1949 p. 1 17).) The latter concept (of 
inference) refers to the process or action of transforming attitudes 
itself. 

Taking this distinction into consideration is very important for Cognitive 
Science. Rules of inference are knowledge entities of a specific type, i.e. 
they are part of the system's (human's) knowledge base. In contrast to 
this, inferences are periormed by the system during information 
processing. The former have to do with the system's potential 
competence or capacities the latter with it's actual performance. 

At this point a relevant pair of questions arises: 

Do humans use valid, i.e. formally justified, inference rules? 
Are human's inferences valid? 



If the answer would be "Yes!" all would be very nice, that means, no 
problems would appear. But a lot of experiments show that humans are 
bad in doing valid inferences; cp. Johnson-Laird's (1983) chapter "How to 



4 



reason syllogistically". Since the answer has to be "No!", In Cognitive 
Science we have two possible reactions with respect to this fact, which 
I want to name as 'conservative" and "liberal": 

conservative reaction: 

Formal systems should not reproduce human"s mistakes. 

liberal reaction: 

Formal systems should describe and explain the inference systems of 
humans, although they are not valid from a logical point of view. 

Because the conservative opinion is - implicitly or explicitly - prevalent 
in the disciplines of logic and formal semantics nearly no cognitively 
relevant contribution to the topic of inference processes have come from 
these fields. On the other hand, most cognitive psychologists, cp. 
Johnson-Laird (1983), agree with the liberal view, but formal inference- 
systems describing and explaining the human competence and 
performance are rare up to now. To develop such systems is one main 
topic of Cognitive Science in the future. With respect to language 
processing this insight is the base of the important remarks on Semdntic 
iniujiion by the logicians and semanti cists Barwise and Cooper (1981): 

"While it Is seldom made explicit, it is sometimes assumed that there 
is some system of axioms and rules of logic engraved on stone tablets 
- that on inference in natural language is valid only if it can be 
formalized by means of these axioms and rules. In actuality, the 
situation is quite the reverse. The native speaker's judgement as to 
whether a certain inference Is correct, whether the truth of the 
hypothesis Implies the truth of the conclusion, is the primary 
evidence of a semantic theory ..." (Barwise/Cooper 1 98 1 ; p. 20 1 -202) 

To sum up the situation: In Cognitive Science and its related disciplines 
different concepts exist of an infereniid} system dependent on the main 
research topics of the discipline In question. Needed is a unified 
treatment of inferences and reasoning processes (cp. Section 4 of this 
paper). 



5. The basic structure of inferential systems 

The mostly investigated and best understood Inferential systems are the 
calculi of formal logic. I will use the structure of these systems to 
exemplify and summarize the basic ideas and to introduce the notation, 
which is used later on. 

Following traditional logics, eg. Carnap (1939) or Tarski (1965), a 
calculus with respect to a formal language L is defined by 



and 



A, a set of sentences, the axioms 
R, a set of rules (of inference). 



Based on this, the concepts of dehvdiions and proofs are defined in the 
wellknown way. The set of all sentences which are derivable fronn A by 
means of rules from R is named as set of theorems: 

Th ( A, R ) := Th R ( A) 

The natural extension of this idea to applied formal systems, i.e. formal 
theories, leads to the deductive method ; cp. Camap (1939), Tarski 
(1965), Kalish/Montague (1964). The language L has to be enriched by 
nonloglcal constants leading to a language L'. Axioms and inference rules 
are defined over L', especially nonlogical axioms are used. By this 
deductive method wide ranges of mathematics and the sciences can be 
treated in a strictly formal manner. 

Let us now continue with a psychologies! interpretation - with respect 
to IPSs - of formal systems. 

A concerns the factual knowledge of the IPS which the 

■^i-ci^, : : system contains in an explicit way (see below), 

R contains the IPS's rules of inference, which determine the 

system's inferential capacity, 

Th r( A) refers to the implicit knowledge of the system, i.e. the 

knowledge entitles which can be reached by derivations 
(or inferences). 



Before I will go on with the explicit - implicit dichotomy I will enter 
into a sketchy discussion of the question what can be inferred (and by 
which methods inferences are performed) by formal systems based on 
standard logics. 

As first test case the natural quantifier MOST is to be mentioned. On the 
one hand, humans perform MOST-inferences very well. Therefore there is 
the need of formal inference-systems to describe and explain the 
phenomena related with liOST-expressions. On the other hand, there exist 
no adequate, fully satisfactory treatment of M(BT in any logical approach 
(cp. Rescher (1962), Kaplan (1966) and Barwise/Cooper (1981) on 
negative results of nosT-formalizations.) Cushing's (1987) two- 
predicate-scope MOST-quantifier is - though interesting from a logial 
point of view - limited w.r.t. explanations of human's hWST-inferences. 

The second example for beyond-traditional-logic inferences concerns 
SEEING. As Barwise/Perry (1983) demonstrate a logic of seeing does 
exist. They postulate an inventory of principles for the behaviour of 
perceptual reports. As an example I will only mention their 

Principle of Veridicality: 

If b sees 9, then ip. (Barwise/Perry 1983; p. 181, 187) 



(Remark: This case concerns so called ' Nl -Percept udl Reports' , where "NT 
stands for "naked infinitive". In the present paper I will not discuss 
advantages and disadvantages of Barwise and Perry's proposal, which is 
under a controversial discussion in linguistics; cp. Higginbothann (1983). 
For my argumentation the type of formalization, not the specific 
solution, is used.) 

The principle of veridicality can be transformed into an inference rule, 
e-g- 

SEE (b,<j») -> <p . , 

Using the same type of formalization an analogous rule should be 
postulated for knowing, namely 

KNOW(a,f)->^ ../.,., ,. 

which is a notational variant of Hintikka's (1962) condition (C.K.) (p. 43) 
in a logic of knowledge. 

What is the moral of these examples of Khrowifffi and SEEING? As I described 
in more detail in another paper (Habel, 1983) there exists a tendency for 
some operators (or concepts) to change their status from beeing non- 
Jogjcd] to becoming iogicaJ . The development of epistemic logic is 
possible only by treating k and b (for Kiwwil^ and believing) as logical 
constants. The trend in future formal systems will be to use more and 
more today-non-logical concepts, e.g. seeing, as logical ones. This means 
that new logics, e.g. a logic of perceptual reports has to be developed in a 
formal manner. (The treatment of SEEING in situation semantics by 
Barwise/Perry - see above - is just a first step on this way.) 

I now will come back to the explicit-implicit distinction. Using the 
interpretation given at the beginning of the present section, namely. 



~ axioms 



~ explicit knowledge 



Tli( A ) ~ theorems 



implicit knowledge 



the relation between these types of knowledge, symbolized by 
Af-A*:=ThR(A) 



Is the relation of derlvsMHtg. In contrast to this, from a psychological 
(or cognitive) point of view another relation and a third type of 
knowledge has to be emphasized, namely the octusUg derived knowledge 
A# produced by and connected via the relation of derivotion . This 
situation (i.e. relation) can be symbolized by 

AhA# 



analogously to the logical relation mentioned above. 

At this point of argumentation some remarks about my use of the logical 
notions Is necessary: The "one-step" relation between two sets of 
formulas F|, F2 which Is Induced by application of one Inference rule 
with respect to the former set Ft resulting In F2 Is usually named as 

deduction or derivation and symbolized by "h". Often an attribute "direct" 
or *1n one step" Is used here. From a logical point of view sequences of 
direct derivations are as Interesting as one-step derivations. Therefore 
the notion of derivdiion (In one or more steps) Is Introduced, formally by 
means of the transitive closure of the relation of direct derivation. 
(Beside of derivation also proof Is used.) But actual derivations or 
proofs are not the major topics of Interest for a logician; Instead of the 
actual derivation the possibility to derive or prove is the topic of 
investigation. Therefore with respect to proof ihe notion of provaMIity 
Is interesting. Because of this specific focussing on the possibility of 
the existence of a derivation, I give emphasis to derivatJIiiy if I 
describe the logical way of Investigating derivations and inferences. 

At this point it should be mentioned that the question whether the 
relation of derivablllty has to be established in a constructive way is 
intensively discussed in the area of logic and proof theory. The details of 
this discussion, which belong to the foundation of mathematics, are 
beyond the subject of the present paper. 

Questions of the type 

How many steps of derivation are needed to ...? 

Which way of derivation is used ...? 

(Both with respect to a pair consisting of a set of axioms and a sentence) 
are very seldom Investigated in traditional logic. (A very interesting 
note on this topic Is Boolos' (1987) paper, which describes a first-order 
Inference rule not feasible practically but usable in a second-order 
variant.) 



4. On the dynamics of Inferential systems 

Given an Inferential system I = < A, R > we can investigate Inferential 
processes with respect to I. Such investigations are concerned with the 
questions stated at the end of the preceding section. Looking at a natural 
inferential system, e.g. a human, the dynamical properties of the system 
are relevant and therefore topics In Cognitive Science. Furthermore, we 
have to take into consideration the distinction (mentioned above) 
between 



a 



A* - the actually derived knowledge 



and 



A * ~ the potentially derivable knowledge 



This distinction is interesting only from the computational point of view: 
A * is the topic of formal logic whereas A# is of major interest in CS 
and Al. A distinction analogous to that between A* and A* is the main 
topic of Levesque's (1984) "Logic of implicit and explicit belief". The 
major differences between his and my approach are: 

Levesque distinguishes explicit and implicit beliefs without dealing 
with the question of processes which make implicit beliefs explicit. 

Levesque does not deal with processes which change beliefs, i.e. he 
does not consider the dynamical properties of knowledge sets (see 
below). 

Only with respect to both types of implicit knowledge, namely A# and 
A*, questions of the type 

Which knowledge entities are derived from A at a specific point of 
time? 

are sensible. 

Beyond the dynamics with respect to specific inferences, i.e. sequences 
of actions, from a cognitive point of view there exists a second type of 
dynamics in inferential systems, namely with respect to the systems. To 
clarify the two types of dynamics i introduce a further theory-internal 
entity, a se^ of points of time 

T={t|} 



I do not want to develop a "theory of time" here. Instead of this 
some relevant properties of T 



list 



1. 

ii. 

iii. 



T is an ordered set (ordering <) 
lis infinite 
T is discrete 



These properties of T reflect the use of time in the following: points of 
time are seen as indices of states of the inferential system. (More 
elaborated time-theories are developed by and described in 
Rescher/Urquhart (1971) and van Benthem (1983).) Furthermore, I claim 
the existence of a minimal element tg, which corresponds to initial 

state. Thus it is possible to use the natural numbers, as a canonical index 
set; cp. also Habel ( 1 985). An interval T" cT of time points, i.e. sets 

T : = Itj, tj] = {t/tj < t & t < tj} 



will be named as time-span. \\ and tj are called beginning time, b(T'), 
and ending time, e(T'), respectively. 

By means of T there exists a natural way to speak about the "Inference 
rule x\ used at tj during an Inference process", and to restrict Inference 

processes with respect to time resources. Given an Inferential system 
< A, R > and a time-span T' c T it is now sensible to define 

ThR(A,r):={S/A ItS} 

similar to the usual definition of Th based on the relation h 
(derlvability) with one important distinction, namely that sets of iime- 
resihcied theorems are based on time-restricted derivations 
characterized as follows: 



Sifr S2 iff 

There exists a sequence of Inference rules which 
constitutes S^ K S2 and there is an index-mapping from F 

into this sequence. 

Remark: "time-restricted set of theorems" and "time-restricted 
derivation" are here not defined in a strict sense; the "definitions" above 
have to be seen as characterizations. In other words, in the present paper 
only the idea of a definition is given in form of sketchy remarks. From 
these characterizations it should be clear, that the cognitively relevant 
set A# representing derived knowledge is of the type described above, 
i.e. A* contains the knowledge entities derived during some time-span T. 
Note, that though A# represents derived knowledge with respect to a 
specific time-span, nothing Is said here about the reasons for deriving 
just the knowledge entities of A# - A (the difference of the knowledge 
sets) during T'. Questions of this type are not topic of the present paper. 

Let me return to T again. Up to now, we used only one sub-set, namely the 
time-span T, of T. In the next extension of the theoretical inventory I 
will make use of specific coverings of T: 

Let T = < T], ... , T|c> be a sequence of time-spans with 
e(Tj) = b(T|+i)for1=1,...k-1 and 

e (T]) = tg , the minimal time-point. 

T is called an initial covering of T. 

By means of such Initial coverings it is possible to characterize 
recursively a sequence of inferential systems and sets of knowledge 
entities: 



10 



Given < A, R >, an inferential system, 
and T = <Ti , ..., 1[^>, an initial covering 

Ai :=A 

Aj+i :=ThR(Aj,T|) 

The dynamical development of derived knowledge can be exemplified 
graphically as follows 



Ai "triAi* 

A 2 1i2 A#2 

A3 "trs A#3 



Thus we have changed from the investigation of one inferential system 
(or formal theory) to sequences of inferential systems. From a cognitive 
point of view it is obvious that the situation in natural inference 
systems are much more complicated than the sketch (given above) 
demonstrates. The most important further extension would concern the 
dynamics of R This means, in contrast to the case described above in 
which every < A j, R > uses the same set of inferential rules R, we have 

to consider the development (over time) of Rj too; i.e. interesting 

(because cognitive realistic) inferential systems have a behaviour of the 
< Aj, Rj>-type. Steps from Rj to Rj+^ can be seen as induced by learning 

processes. (Cp. Emde/Habel/Rollinger 1983 , Habel i. prep.) 



5. Conclusion: Mutual relation between logics and psLjchology 

In this concluding section I will summarize the main results and insights 
which should be influential between the poles "logic' and 'psychology" of 
the Cognitive Science spectrum. Furthermore, I will formulate some 
mutual requirements. 

Logic and "theoretical AT have a lot of results on the formal properties of 
information processing systems, especially inferential systems. These 
results concern e.g. problems of decidability, generative capacity and 
complexity. From a cognitive point of view there are some desiderata, 
e.g. with respect to the dynamics of inferential processes and systems. 
Furthermore, traditionally only some phenomena of human knowledge 
processing are subject of logic. For example, beyond the standard 
quantifiers "all" and "some" only few results exist (cp. the remarks on most 
in section 3). In contrast, psychology offers empirical data and 
theoretical models with respect to derivations by natural inference 
systems. The formal analysis of the psychologist's models requires 



11 



methods from logic and theoretical Al. That formal analysis is useful 
demonstrates the example of "mosf-inferences. Up to now no fullly 
adequate formal treatment of "most" does exist. The most promising 
approaches can be classified into two types of cdrdfnaJiiy approaches 
vs. default-approaches .'[Xk^ former class contains the formalizations of 
Rescher ( 1 962), Kaplan ( 1 964), Barwise/Cooper (1 98 1 ), the latter Reiter 
(1980). Both types of formalizations have been investigated with respect 
to formal properties, e.g. decidability or existence of proof-procedures. 
Such formal results concern the topic of theoretical evidences 
mentioned in section 1: e.g. lower "theoretical cost" of one formal system 
w.r.t. another could possibly correspond to lower cognitive costs of the 
natural inference systems in question. And by this could be explained why 
the cheaper system is selected in spite of missing validity (in a formal 
sense). (The usefulness of theoretical evidences for Cognitive Science 
will be the topic of a future paper.) 



References: 



■•■ Ti?!:' 



Barwise, John/Cooper, Robin (1981): 

Generalized Quantifiers and Natural Language. Linguistics and 
Philosophy 4 (2). 159-219. 

Barwise, John/Perry, J. ( 1 983): 

Situations and Attitudes. Bradford Books: MIT Cambridge, Mass. 

vanBenthem, J.F. (1983): 

The Logic of Time. Reidel: Dordrecht 

Boolos, George (1987): 

A Cun'ous inference . Journo^ of Philological Logic 16. 1-12. 

Camap, Rudolf (1939): 

Foundation of Logic and Mathematics. Encyclopedia of Unified 
Science, Vol I, No 3: Chicago 

Churchland, Paul M. (1984): 

Matter and Consciousness. MIT-Press: Cambridge, Mass. 

Cushing, Steven (1987): 

Some Quantifiers Require Two-Predicate Scopes . Arti f i ci al 
Intelligence 32, 259-67 

Drever, James (rev. ed. 1964): 

The Penguin Dictionary of Psychology. Penguin: Harmondsworth. 



Emde, Werner/ Habel, Christopher/ Rollinger, Claus-Rainer(1983): 
The discovery of the equator or concept driven learning. Proc. 8th 
IJCAI. 455-458. 



12 



Habel, Christopher (1983): 

Logjsche Sy si erne und Represent at ionsprot I erne 

in: B. Neumann (ed): GWAI-83. Springer: Berlin. 1 1 8-42 

Habel, Christopher (1985): 

Referential Nets 8S Knowledge Structures . in: Th. Ballmer (ed): 
Linguistic Dynamics, de Gruyter: Berlin, p. 62-84 

Habel, Christopher (i. prep.); 

A note on the dynamics of rule systems. 

Haugeland, John (1978): 

The Nature and Plausitility of Cogniijvism . in: J. Haugeland (ed): 
Mind Design. Bradford: Montgomary Vt. 243-81 

Higginbotham, James ( 1 983): 

The logic of perceptual reports: An exiensional alternative to 
Situation Semantics Journal of Philosophy 80(2). 100-27 

Hintikka,Jaakko(1962): 

Knowledge and Belief. Cornell Univ. Press: Ithaka, NY. 

Johnson-Laird, P.N. (1983): 

Mental Models. Cambridge UP: Cambridge. 

Kalish, Donald /Montague, Richard (1964): 

Logic-Techniques of formal reasoning. Harcourt, Brace & World: New 
York. 

Kaplan, David (1966): 

Rescher's piuraiitg Quantification .Jo\in\ti\ of Symbolic Logic 31. 
153-4 



Levesque, Hector J. (1984): 

A Logic of implicit and Explicit Beiief. k^M 1984: 198-202 

Newell, Allen (1980): 

Physical Symtoi Systems . Cognitive Science 4: 135-83 

Pylyshyn, Zenon (1984): 

Computation and Cognition. Bradford MIT-Press: Cambridge, Mass. 

Reiter, R. (1980): 

A I ogic for Default Reasoning. Arti f i ci al I ntel 1 i gence 13: 8 1 - 1 32. 

Rescher, Nicholas (1962): 

Plurality Quantification. Journal of Symbolic Logic 27: p. 373-4. 

Rescher, Nicholas/Urquhart, Alasdair (1971): 
Temporal Logic. Springer: Wien. 



13 



Ryle, Gilbert (1949/1973): 

The Concept of Mind. Penguin University Books: Harmondsworth, 
Middlesex. 

Tarski, Alfred (1965): 

Introduction to Logic. Oxford UP: New York 



Author's Note: 

The author's address is: Christopher Habel, Universitat Hamburg, 

Fachbereich Infomrjatik, Bodenstedtstr. 16, D-2000 Hamburg 50, Fed. Rep. 

Germany. 

An earlier version of this paper was presented at a symposium on 

Knowledge Representation at the 35th Annual Meeting of the German 

Psychological Society (Deutsche Gesellschaft fur Psychologie) in 

September 1986.